﻿#define  _CRT_SECURE_NO_WARNINGS 1
//day 01
//数字统计	
#include <iostream>
#include <string>
using namespace std;

int main()
{
    int l, r;
    cin >> l >> r;

    int cnt = 0;
    for (int i = l; i <= r; i++)
    {
        string s = to_string(i);
        for (auto e : s)
        {
            if (e == '2')
                cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

//两个数组的交集
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
    vector<int> res;
    unordered_set<int> s1(nums1.begin(), nums1.end());
    unordered_set<int> s2(nums2.begin(), nums2.end());

    for (auto e : s1)
    {
        if (s2.count(e) == 1)
        {
            res.push_back(e);
        }
    }

    return res;
}

//点击消除
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    string s;
    cin >> s;

    string st;
    for (auto e : s)
    {
        if (st.empty())
        {
            st.push_back(e);
        }
        else
        {
            if (st.back() == e)
            {
                st.pop_back();
            }
            else
            {
                st.push_back(e);
            }
        }
    }

    if (st == "")   cout << 0 << endl;
    else cout << st << endl;

    return 0;
}

// day 02
//牛牛的快递
#include <iostream>
using namespace std;

//Learn：
//ceil()--向上取整
//floor()--向下取整

int main()
{
    double weight;
    char emrflag;
    cin >> weight >> emrflag;

    long long res = 0;
    if (weight <= 1)
    {
        res = 20;
    }
    else
    {
        res = 20 + (long long)(weight - 1);
        if (weight - (long long)(weight) > 0)
        {
            res++;
        }
    }

    if (emrflag == 'y')
    {
        res += 5;
    }
    cout << res << endl;
    return 0;
}

//最⼩花费爬楼梯
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    vector<int> cost(n);
    for (int i = 0; i < n; i++)
    {
        cin >> cost[i];
    }

    vector<int> dp(n + 1);
    for (int i = 2; i <= n; i++)
    {
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }

    cout << dp[n] << endl;
}


//数组中两个字符串的最小距离
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    if (n < 2)
    {
        cout << -1 << endl;
        return 0;
    }
    string str1, str2;
    cin >> str1 >> str2;

    vector<string> strs(n);
    for (int i = 0; i < n; i++)
    {
        cin >> strs[i];
    }

    int cur1 = 0, cur2 = 0;
    int res = 0x3f3f3f3f;
    bool flag = true;
    while (cur1 < strs.size() && cur2 < strs.size())
    {
        while (cur1 < strs.size() && strs[cur1] != str1)
        {
            cur1++;
        }

        while (cur2 < strs.size() && strs[cur2] != str2)
        {
            cur2++;
        }

        if (cur1 >= strs.size() || cur2 >= strs.size())
        {
            break;
        }

        if (cur2 > cur1)
        {
            res = min(res, abs(cur2 - cur1));
            cur1 = cur2 + 1;
        }
        else if (cur2 < cur1)
        {
            res = min(res, abs(cur2 - cur1));
            cur2++;
        }

    }

    cout << (res == 0x3f3f3f3f ? -1 : res) << endl;

    return 0;
}

//day 03
//简写单词
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    vector<string> words;
    string tmp;
    while (cin >> tmp)
    {
        words.push_back(tmp);
    }

    for (auto& e : words)
    {
        cout << (char)toupper(e[0]);
    }
    cout << endl;
    return 0;
}

//dd爱框框
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

struct res
{
    int dist = 0x3f3f3f3f;
    int l;
    int r;
};

int main()
{
    int n, x;
    cin >> n >> x;

    vector<int> datas(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> datas[i];
    }

    int l = 1, r = 1;
    int sum = 0;
    res ans;
    while (r <= n)
    {
        if (sum < x)
        {
            sum += datas[r];
            r++;
        }
        else
        {
            if (r - l < ans.dist)
            {
                ans.dist = r - l;
                ans.l = l;
                ans.r = r - 1;
            }
            sum -= datas[l];
            l++;

        }
    }

    cout << ans.l << " " << ans.r;
    return 0;
}

//除2！
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    long long n, k;
    cin >> n >> k;

    long long sum = 0;
    priority_queue<long long> odds;
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        if (t % 2 == 0)
        {
            odds.push(t);
        }
        sum += t;    //sum先全都加，后面再减即可
    }

    while (!odds.empty() && k--)
    {
        long long t = odds.top() / 2;
        odds.pop();

        if (t % 2 == 0)
        {
            odds.push(t);
        }
        sum -= t;
    }

    //若最后再不断pop遍历堆，由于需要调整，会超时！
    cout << sum;
    return 0;
}

//day 04
//Fibonacci数列
#include <iostream>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;

    int prev = 1;
    int cur = 1;
    int next = 2;

    while (cur < n)
    {
        prev = cur;
        cur = next;
        next = prev + cur;
    }

    cout << ((n - prev > cur - n) ? (cur - n) : (n - prev)) << endl;

    return 0;
}

//单词搜索
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int m = 0;
int n = 0;
bool vis[101][101];
bool res = false;
void dfs(vector<string>& board, string word, int i, int j, int cur)
{
    if (word.size() == cur)
    {
        res = true;
        return;
    }

    for (int k = 0; k < 4; k++)
    {
        int x = dx[k] + i;
        int y = dy[k] + j;
        if ((x >= 0 && x < m) && (y >= 0 && y < n)
            && board[x][y] == word[cur] && !vis[x][y])
        {
            vis[x][y] = true;
            dfs(board, word, x, y, cur + 1);
            vis[x][y] = false;
        }
    }
    return;
}

bool exist(vector<string>& board, string word)
{
    m = board.size();
    n = board[0].size();
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (res)
            {
                break;
            }
            if (board[i][j] == word[0])
            {
                vis[i][j] = true;
                dfs(board, word, i, j, 1);
                vis[i][j] = false;
            }
        }
    }

    return res;
}

//杨辉三角
#include <iostream>
using namespace std;

int main()
{
    int res[35][35] = { 0 };
    res[1][1] = 1;

    int n = 0;
    cin >> n;

    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            res[i][j] = res[i - 1][j] + res[i - 1][j - 1];
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            printf("%5d", res[i][j]);
        }
        cout << endl;
    }
    return 0;
}

//day 05
//游游的you
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        long long a, b, c;
        long long res = 0;
        cin >> a >> b >> c;

        int com = min({ a,b,c });
        b -= com;
        res += com * 2;

        res += (b - 1 >= 0 ? b - 1 : 0);
        cout << res << endl;
    }

    return 0;
}

//腐烂的苹果
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
bool vis[1005][1005];
int m = 0;
int n = 0;

using pii = pair<int, int>;

int rotApple(vector<vector<int> >& grid) {
    m = grid.size();
    n = grid[0].size();
    int res = 0;
    queue<pii> q;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) {
                q.push({ i, j });
            }
        }
    }
    while (!q.empty()) {
        res++;
        int time = q.size();
        while (time--) {
            auto [a, b] = q.front();
            vis[a][b] = true;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int x = a + dx[i];
                int y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) {
                    grid[x][y] = 2;
                    q.push({ x, y });
                }
            }
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                return -1;
            }
        }
    }

    return res - 1;
}

//孩⼦们的游戏(圆圈中最后剩下的数)
int LastRemaining_Solution(int n, int m)
{
    vector<int> child(n);
    int flag = n - 1;
    int s = 0;
    int cnt = 0;
    while (flag > 0)
    {
        if (cnt == m - 1 && child[s] == 0)
        {
            child[s] = 1;
            flag--;
            cnt = 0;
        }
        else if (child[s] == 0)
        {
            ++cnt;
        }

        if (++s >= n)
        {
            s = 0;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (child[i] == 0)
        {
            return i;
        }
    }

    return -1;
}

//day06
//大数加法
string solve(string s, string t)
{
    string res;
    int ends = s.size() - 1;
    int endt = t.size() - 1;
    int carry = 0;
    while (ends >= 0 && endt >= 0)
    {
        int tmp = s[ends] - '0' + t[endt] - '0' + carry;
        if (tmp >= 10)
        {
            carry = 1;
            tmp %= 10;
        }
        else
        {
            carry = 0;
        }
        res += to_string(tmp);
        ends--; endt--;
    }

    while (ends >= 0)
    {
        int tmp = s[ends] - '0' + carry;
        if (tmp >= 10)
        {
            carry = 1;
            tmp %= 10;
        }
        else
        {
            carry = 0;
        }
        res += to_string(tmp);
        ends--;
    }
    while (endt >= 0)
    {
        int tmp = t[endt] - '0' + carry;
        if (tmp >= 10)
        {
            carry = 1;
            tmp %= 10;
        }
        else
        {
            carry = 0;
        }
        res += to_string(tmp);
        endt--;
    }

    if (carry != 0)
    {
        res += "1";
    }

    reverse(res.begin(), res.end());

    return res;
}

//链表相加(二)
ListNode* addInList(ListNode* head1, ListNode* head2)
{
    string s1, s2;
    ListNode* cur = head1;
    while (cur)
    {
        s1 += to_string(cur->val);
        cur = cur->next;
    }
    cur = head2;
    while (cur)
    {
        s2 += to_string(cur->val);
        cur = cur->next;
    }

    string rs = solve(s1, s2);
    ListNode* res = new ListNode(rs[0] - '0');
    ListNode* rear = res;
    for (int i = 1; i < rs.size(); i++)
    {
        ListNode* newnode = new ListNode(rs[i] - '0');
        rear->next = newnode;
        rear = rear->next;
    }

    return res;
}

//大数乘法
string solve(string s, string t)
{
    string unit = "";
    string sum = "";

    int i2 = t.size() - 1;
    while (i2 >= 0)
    {
        int i1 = s.size() - 1;
        int carry = 0;
        string product = "";
        while (i1 >= 0)
        {
            product += (((t[i2] - '0') * (s[i1] - '0') + carry) % 10) + '0';
            carry = ((t[i2] - '0') * (s[i1] - '0') + carry) / 10;
            i1--;
        }
        if (carry != 0)
        {
            product += carry + '0';
        }
        std::reverse(product.begin(), product.end());
        product += unit;
        sum = solveadd(sum, product);
        unit += '0';
        i2--;
    }

    if (sum[0] == '0')
    {
        return "0";
    }
    return sum;
}


//day 07
//在字符串中找出连续最长的数字串
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int start = 0;
    int len = 0;

    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
        {
            int pos = i;
            while (i < s.size() && s[i] >= '0' && s[i] <= '9')
                i++;
            if (i - pos > len)
            {
                start = pos;
                len = i - pos;
            }
        }
    }

    cout << s.substr(start, len) << endl;
    return 0;
}

//岛屿数量
using pii = pair<int, int>;
queue<pii> q;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int m, n;
int vis[301][301];

void bfs(vector<vector<char> >& grid)
{
    while (!q.empty())
    {
        auto [a, b] = q.front();
        q.pop();

        for (int k = 0; k < 4; k++)
        {
            int x = a + dx[k];
            int y = b + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
            {
                vis[x][y] = true;
                q.push({ x,y });
            }
        }
    }
}

int solve(vector<vector<char> >& grid)
{
    int res = 0;
    m = grid.size();
    n = grid[0].size();

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == '1' && !vis[i][j])
            {
                q.push({ i,j });
                vis[i][j] = true;
                bfs(grid);
                res++;
            }
        }
    }

    return res;
}

//拼三角
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//没有贪心，不能只枚举一次
//通过排序来优化枚举过程 --> 可以直接硬编码！！！
int main()
{
    int n = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        vector<long long> datas(6);
        for (int j = 0; j < 6; j++)
        {
            cin >> datas[j];
        }
        sort(datas.begin(), datas.end());

        if ((datas[0] + datas[1] > datas[2] && datas[3] + datas[4] > datas[5])
            || (datas[0] + datas[4] > datas[5] && datas[1] + datas[2] > datas[3])
            || (datas[0] + datas[2] > datas[3] && datas[1] + datas[4] > datas[5])
            || (datas[0] + datas[3] > datas[4] && datas[1] + datas[2] > datas[5]))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    return 0;
}

//day08
//求最小公倍数
#include <iostream>
using namespace std;

long long getGcd(long long a, long long b)
{
    long long tmp = a % b;
    while (tmp)
    {
        a = b;
        b = tmp;
        tmp = a % b;
    }

    return b;
}

int main()
{
    long long a, b;
    cin >> a >> b;

    cout << a * b / getGcd(a, b) << endl;
    return 0;
}

//数组中的最长连续子序列
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    vector<int> data(n);
    for (int i = 0; i < n; i++)
    {
        cin >> data[i];
    }
    sort(data.begin(), data.end());

    int len = 1;
    int cnt = 1;
    int i = 0, j = 1;
    while (j < n)
    {
        if (data[j] - data[j - 1] == 1)
        {
            cnt++;
        }
        else if (data[j] - data[j - 1] > 1)
        {
            len = max(len, cnt);
            i = j;
            cnt = 1;
        }
        j++;
    }
    len = max(len, cnt);
    cout << len << endl;

    return 0;
}

//字母收集
#include <iostream>
#include <vector>
using namespace std;

int scoreHash(char c)
{
    switch (c)
    {
    case 'l':
        return 4;
    case 'o':
        return 3;
    case 'v':
        return 2;
    case 'e':
        return 1;
    }
    return 0;
}

int main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<int>> dp(n, vector<int>(m));
    vector<vector<char>> matrix(n, vector<char>(m));


    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> matrix[i][j];
        }
    }

    dp[0][0] = scoreHash(matrix[0][0]);
    for (int i = 1; i < n; i++)
    {
        dp[0][i] += scoreHash(matrix[0][i]) + dp[0][i - 1];
        dp[i][0] += scoreHash(matrix[i][0]) + dp[i - 1][0];
    }

    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + scoreHash(matrix[i][j]);
        }
    }

    cout << dp[n - 1][m - 1] << endl;
    return 0;
}

//day09
//添加逗号
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string s;
    cin >> s;
    string res;
    int cnt = 0;
    for (int i = s.size() - 1; i >= 0;)
    {
        if (cnt == 3)
        {
            res += ',';
            cnt = 0;
        }
        else
        {
            res += s[i];
            cnt++;
            i--;
        }
    }

    reverse(res.begin(), res.end());
    cout << res << endl;
}

//跳台阶
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[n] << endl;
}

//扑克牌顺子
bool IsContinuous(vector<int>& numbers)
{
    sort(numbers.begin(), numbers.end());

    int cnt_zero = 0;
    int i = 0;
    while (numbers[i] == 0)
    {
        i++;
        cnt_zero++;
    }

    if (i == 4)
    {
        return true;
    }

    for (int j = 4; j > i; j--)
    {
        if (numbers[j] - numbers[j - 1] - 1 > cnt_zero)
        {
            return false;
        }
        else if (numbers[j] - numbers[j - 1] == 0)
        {
            return false;
        }
        else
        {
            cnt_zero -= numbers[j] - numbers[j - 1] - 1;
        }
    }

    return true;
}

//day10
//最长回文子串
bool dp[1005][1005];
int getLongestPalindrome(string A)
{
    int n = A.size();
    int res = 0;
    for (int j = 0; j < n; j++)
    {
        for (int i = n - 1; i >= 0; i--)
        {
            if (A[i] == A[j])
            {
                if (i == j || i + 1 == j)
                {
                    dp[i][j] = true;
                }
                else
                {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }

            if (dp[i][j])
            {
                res = max(res, j - i + 1);
            }
        }
    }

    return res;
}

//买卖股票的最好时机(一)
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> prices(n);
    for (int i = 0; i < n; i++)
    {
        cin >> prices[i];
    }

    int prevmin = prices[0];
    int res = 0;
    for (int i = 1; i < prices.size(); i++)
    {
        res = max(prices[i] - prevmin, res);
        prevmin = min(prices[i], prevmin);
    }

    cout << res << endl;
    return 0;
}

//过河卒
#include <vector>
#include <iostream>
using namespace std;

long long dp[25][25] = { 0 };
int board[25][25] = { 0 };
int dx[8] = { 1,1,-1,-1,2,2,-2,-2 };
int dy[8] = { -2,2,-2,2,1,-1,1,-1 };
int main()
{
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    if (x == 0 && y == 0)
    {
        cout << 0 << endl;
        return 0;
    }

    board[x][y] = -1;
    for (int i = 0; i < 8; i++)
    {
        int x1 = dx[i] + x;
        int y1 = dy[i] + y;
        board[x1][y1] = -1;
    }

    for (int j = 1; j <= m; j++)    //注意这里不是一整行一整列都能更新成1！
    {
        if (board[0][j] != -1)
            dp[0][j] = 1;
        else
            break;
    }
    for (int i = 1; i <= n; i++)
    {
        if (board[i][0] != -1)
            dp[i][0] = 1;
        else
            break;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (board[i][j] == -1)
            {
                continue;
            }

            if (board[i - 1][j] != -1)
            {
                dp[i][j] += dp[i - 1][j];
            }
            if (board[i][j - 1] != -1)
            {
                dp[i][j] += dp[i][j - 1];
            }
        }
    }

    cout << dp[n][m] << endl;
    return 0;
}

//day11
//游游的水果大礼包
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//x，y的枚举
int main()
{
    long long n, m, a, b;
    cin >> n >> m >> a >> b;

    long long val = 0;
    for (long long x = 0; x <= min(n / 2, m); x++)
    {
        long long y = min(n - 2 * x, (m - x) / 2);    //剩下的直接取，但也要按最小的计算
        val = max(val, a * x + b * y);
    }

    cout << val << endl;

    return 0;
}

//买卖股票的最好时机(二)
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    vector<int> prices(n);
    for (int i = 0; i < n; i++)
    {
        cin >> prices[i];
    }

    vector<vector<int>> dp(n, vector<int>(2));

    dp[0][1] = -prices[0];
    for (int i = 1; i < n; i++)
    {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }

    cout << max({ dp[n - 1][0], dp[n - 1][1], dp[n - 1][2] }) << endl;
}

//倒置字符串
#include <iostream>
#include <algorithm>
#include <sstream>
#include <vector>
using namespace std;

int main()
{
    string s;
    getline(cin, s);
    stringstream ss(s);

    vector<string> vs;
    string tmp;
    while (ss >> tmp)
    {
        vs.push_back(tmp);
    }

    string res;
    for (int i = vs.size() - 1; i >= 0; i--)
    {
        res += vs[i];
        if (i != 0)
        {
            res += " ";
        }
    }

    cout << res << endl;

    return 0;
}

//day12
//删除公共字符
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main()
{
    string s;
    getline(cin, s);

    string del;
    cin >> del;

    unordered_set<char> hash(del.begin(), del.end());

    string res;
    for (auto e : s)
    {
        if (hash.count(e) == 0)
        {
            res += e;
        }
    }

    cout << res << endl;
    return 0;
}

//两个链表的第一个公共结点
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2)
{
    ListNode* cur = pHead1;
    int len1 = 0;
    while (cur)
    {
        len1++;
        cur = cur->next;
    }

    cur = pHead2;
    int len2 = 0;
    while (cur)
    {
        len2++;
        cur = cur->next;
    }

    ListNode* mov1 = pHead1;
    ListNode* mov2 = pHead2;
    if (len1 > len2)
    {
        while (len1 > len2 && mov1 != mov2)
        {
            mov1 = mov1->next;
            len1--;
        }
    }
    else if (len1 < len2)
    {
        while (len1 < len2 && mov1 != mov2)
        {
            mov2 = mov2->next;
            len2--;
        }
    }

    //到这保证两链表剩余长度一定相等
    while (mov1 && mov2)
    {
        if (mov1 != mov2)
        {
            mov1 = mov1->next;
            mov2 = mov2->next;
        }
        else
        {
            break;
        }
    }

    return mov1;
}

//mari和shiny
#include <iostream>
#include <vector>
using namespace std;

//坑：没注意计算数据范围，最长可能需要10^15，故需要long long
int main()
{
    int n;
    cin >> n;

    vector<char> arr(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    long long res = 0;
    long long s_cnt = 0;
    long long h_cnt = 0;
    long long y_cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 's')
        {
            s_cnt += 1;
        }
        else if (arr[i] == 'h')
        {
            h_cnt = s_cnt + h_cnt;
        }
        else if (arr[i] == 'y')
        {
            res += h_cnt;
        }
    }

    cout << res << endl;
    return 0;
}

//day13
//牛牛冲钻五
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, k;
        cin >> n >> k;

        string grades;
        cin >> grades;

        int mov = 0;
        int origin = 0;
        int wins = 0;
        for (int i = 0; i < n; i++)
        {
            if (grades[i] == 'W')
            {
                wins++;
                if (wins >= 3)
                {
                    origin += k;
                }
                else
                {
                    origin++;
                }
            }
            else
            {
                origin--;
                wins = 0;
            }
        }

        cout << origin << endl;
    }

    return 0;
}

//最长无重复子数组
int maxLength(vector<int>& arr)
{
    unordered_map<int, int> hash;
    int left = 0, right = 0;
    int res = 0;
    while (right < arr.size())
    {
        if (hash.count(arr[right]) == 0)
        {
            hash[arr[right]] = right;
            right++;
        }
        else
        {
            res = max(res, right - left);
            int end = hash[arr[right]];
            while (left <= end)
            {
                hash.erase(arr[left]);
                left++;
            }
        }
    }
    res = max(res, right - left);

    return res;
}

//重排字符串
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;

    int hash[26] = { 0 };
    char maxc = 0;
    int maxn = 0;
    for (int i = 0; i < n; i++)
    {
        if (++hash[s[i] - 'a'] > maxn)
        {
            maxn = hash[s[i] - 'a'];
            maxc = s[i];
        }
    }

    if (maxn > (n + 1) / 2)
    {
        cout << "no";
        return 0;
    }

    vector<char> res(n, 0);
    int i = 0;
    while (hash[maxc - 'a']-- > 0)
    {
        res[i] = maxc;
        i += 2;
    }

    int mov = i;
    for (int j = 0; j < 26; j++)
    {
        while (hash[j]-- > 0)
        {
            if (mov >= n)
            {
                mov = 1;
            }
            if (res[mov] == 0)
            {
                res[mov] = j + 'a';
            }
            mov += 2;
        }
    }

    cout << "yes" << endl;
    for (auto e : res)
    {
        cout << e;
    }
    return 0;
}

//day14
//乒乓球筐
//可以只用一个哈希表
//注意多组数据输入，除了用while循环进行多组输入，注意循环内不能return 0 ！！！
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main()
{
    string s1, s2;
    while (cin >> s1 >> s2)
    {
        unordered_map<char, int> hash1;
        unordered_map<char, int> hash2;
        bool ret = true;

        for (auto e : s1)
        {
            hash1[e]++;
        }
        for (auto e : s2)
        {
            hash2[e]++;
        }

        for (auto& e : hash2)
        {
            if (hash1.count(e.first) == 0 || hash1[e.first] < e.second)
            {
                ret = false;
                break;
            }
        }

        cout << (ret ? "Yes" : "No") << endl;
    }

    return 0;
}

//组队竞赛
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<long long> data(n * 3);
    for (int i = 0; i < n * 3; i++)
    {
        cin >> data[i];
    }

    sort(data.begin(), data.end());

    int mov = n * 3 - 2;
    long long res = 0;
    while (n--)
    {
        res += data[mov];
        mov -= 2;
    }

    cout << res << endl;
    return 0;
}

//删除相邻数字的最大分数
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    vector<int> data(n);
    int maxn = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> data[i];
        maxn = max(data[i], maxn);
    }

    //sort(data.begin(), data.end());
    vector<int> hash(maxn + 1);
    for (int i = 0; i < n; i++)
    {
        hash[data[i]] += data[i];
    }

    vector<vector<int>> dp(maxn + 1, vector<int>(2));
    dp[1][0] = 0;
    dp[1][1] = hash[data[1]];
    for (int i = 1; i <= maxn; i++)
    {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + hash[i];
    }
    // for(int i = 0; i <= maxn; i++)
    // {
    //     for(int j = 0; j < 2; j++)
    //     {
    //         cout << dp[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    cout << max(dp[maxn][0], dp[maxn][1]) << endl;

    return 0;
}

//day15
//平方数
#include <cmath>
#include <iostream>
using namespace std;

int main()
{
    long long x;
    cin >> x;

    long long y = sqrt(x);
    long long prev = pow(y, 2);
    long long next = pow(y + 1, 2);

    long long res = (x - prev < next - x) ? prev : next;
    cout << res << endl;

    return 0;
}

//分组
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

//每组 “最大” 安排d个人
bool check(int d, int m, unordered_map<int, int>& hash)
{
    int total = 0;
    for(auto& e : hash)
    {
        total += e.second / d + (e.second % d == 0 ? 0 : 1);
    }
    
    return total <= m;    
    //因为d定义的是每组以“最大”的人数去填充，故遍历时很可能就没有等于m的情况，
    //如：a声部6人，b声部3人，要求分4组；当d为2时，total为5；当d为3时，total为3；
    //由上，total的值不一定等于m。这是由于按“最大”去分，但实际上可以不需要每组都达到“最大”
    //故是 <=
    
    //同理可以理解二分过程，不一定就有=m的“mid点”，当right到达那个“最接近的点”后，上面例子
    //来看就是3，接下来就一直是left在往右走了，直到它们重合，循环结束
}

int main()
{
    int n,m;
    cin >> n >> m; 
    unordered_map<int, int> hash;
    int hmax = 0;
    for(int i = 0; i < n; i++)
    {
        int a = 0;
        cin >> a;
        hmax = max(hmax, ++hash[a]);
    }
    
    int res = 0;
    //BF
    for(int i = 1; i <= hmax; i++)
    {
        if(check(i,m,hash))
        {
            res = i;
            break;
        }
    }
    cout << (res == 0 ? -1 : res) << endl;
    
    //Binary
//     int left = 1;
//     int right = hmax;
//     while(left < right)
//     {
//         int mid = left + (right - left)/2;
//         if(check(mid,m,hash))
//         {
//             right = mid;
//         }
//         else
//         {
//             left = mid + 1;    
//         }
//     }
    
//     if(hash.size() > m)
//     {
//         cout << -1 << endl;
//     }
//     else
//     {
//         cout << left << endl;
//     }
    return 0;
}

//【模板】拓扑排序
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    unordered_map<int, vector<int>> edges;
    vector<int> degree(n + 1);

    for (int i = 0; i < m; i++)
    {
        int from, to;
        cin >> from >> to;
        edges[from].push_back(to);
        degree[to]++;
    }

    queue<int> q;
    vector<int> res;
    for (int i = 1; i <= n; i++)
    {
        if (degree[i] == 0)
        {
            q.push(i);
            res.push_back(i);
        }
    }

    while (!q.empty())
    {
        int node = q.front();
        q.pop();

        for (auto nextnode : edges[node])
        {
            if (--degree[nextnode] == 0)
            {
                q.push(nextnode);
                res.push_back(nextnode);
            }
        }
    }

    if (res.size() != n)
    {
        cout << -1 << endl;
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            cout << res[i];
            if (i < n - 1)
            {
                cout << " ";
            }
        }
        cout << endl;
    }

    return 0;
}

//day16
//字符串替换
string formatString(string str, vector<char>& arg)
{
    string res;
    int i = 0;
    int argi = 0;
    while (i < str.size())
    {
        if (str[i] != '%')
        {
            res += str[i];
            i++;
        }
        else
        {
            res += arg[argi++];
            i += 2;
        }
    }

    for (int j = argi; j < arg.size(); j++)
    {
        res += arg[j];
    }

    return res;
}

//神奇数
#include <cmath>
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

unordered_set<int> prims;

bool IsPrime(int num)
{
    for (int i = 2; i <= sqrt(num); i++)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    for (int i = 2; i <= 100; i++)
    {
        if (IsPrime(i))
        {
            prims.insert(i);
        }
    }

    int a, b;
    cin >> a >> b;

    int cnt = 0;
    for (int k = a; k <= b; k++)
    {
        if (k < 10 && IsPrime(k))
        {
            cnt++;
            continue;
        }
        if (k < 100 && prims.count(k) == 1)
        {
            cnt++;
            continue;
        }

        string tmp = to_string(k);
        for (int i = 0; i < tmp.size(); i++)
        {
            bool flag = false;
            for (int j = i + 1; j < tmp.size(); j++)
            {
                string s1 = "", s2 = "";
                s1 += tmp[i];
                s1 += tmp[j];
                s2 += tmp[j];
                s2 += tmp[i];
                int num1 = stoi(s1);
                int num2 = stoi(s2);
                if ((prims.count(num1) && num1 > 10) || (prims.count(num2) && num2 > 10))
                {
                    cnt++;
                    flag = true;
                    break;
                }
            }
            if (flag)    break;
        }
    }

    cout << cnt << endl;
    return 0;
}

//DNA序列
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    string str;
    int n;
    cin >> str >> n;

    float a = 0;
    for (int i = 0; i < n; i++)
    {
        if (str[i] == 'C' || str[i] == 'G')
        {
            a++;
        }
    }
    float rate = a / n;
    int left = 1;
    int right = n;
    int rpos = 0;

    //因为长度固定，故只关心左右即可！
    //左边只关注有没有一个C或G移出窗口，右边只关注有没有一个C或G加入窗口
    while (right < str.size())
    {
        if (str[left - 1] == 'C' || str[left - 1] == 'G')    a--;
        if (str[right] == 'C' || str[right] == 'G') a++;

        if (a / n > rate)
        {
            rate = a / n;
            rpos = left;
        }
        left++;
        right++;
    }

    cout << str.substr(rpos, n) << endl;
    return 0;
}

//day 17
//小乐乐改数字
#include <iostream>
using namespace std;

int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        if ((s[i] - '0') % 2 == 0)
        {
            s[i] = '0';
        }
        else
        {
            s[i] = '1';
        }
    }

    cout << stoi(s) << endl;
}

//十字爆破
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m
        vector<long long> row_sum(n);
    vector<long long> col_sum(m);
    vector<vector<long long>> data(n, vector<long long>(m));

    for (int i = 0; i < n; i++)
    {
        long long sum = 0;
        for (int j = 0; j < m; j++)
        {
            cin >> data[i][j];
            sum += data[i][j];
        }
        row_sum[i] = sum;
    }

    for (int j = 0; j < m; j++)
    {
        long long sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += data[i][j];
        }
        col_sum[j] = sum;
    }

    //vector<vector<int>> res(n,vector<int>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << col_sum[j] + row_sum[i] - data[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

//比那名居的桃子
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    vector<long long> happy_val(n);
    vector<long long> shame_val(n);
    for (int i = 0; i < n; i++)
    {
        cin >> happy_val[i];
    }
    for (int i = 0; i < n; i++)
    {
        cin >> shame_val[i];
    }

    //滑动窗口，从第i天吃所能获得的快乐值和羞耻值
    vector<long long> happy_res(n);
    vector<long long> shame_res(n);
    for (int i = 0; i < k; i++)
    {
        happy_res[0] += happy_val[i];
        shame_res[0] += shame_val[i];
    }

    int left = 1; int right = k;
    while (right < n)
    {
        happy_res[left] = happy_res[left - 1] - happy_val[left - 1] + happy_val[right];
        shame_res[left] = shame_res[left - 1] - shame_val[left - 1] + shame_val[right];
        left++;
        right++;
    }
    happy_res[left] = happy_val[left];
    shame_res[left] = shame_val[left];

    // for(int i = 0; i < n; i++)
    // {
    //     cout << happy_res[i] << " ";
    // }
    // cout << endl;
    // for(int i = 0; i < n; i++)
    // {
    //     cout << shame_res[i] << " ";
    // }
    // cout << endl;
    //筛选结果
    long long res = 0;      //注意是下标
    for (int i = 0; i < n; i++)
    {
        if (happy_res[i] > happy_res[res])
        {
            res = i;
        }
        else if (happy_res[i] == happy_res[res])
        {
            if (shame_res[i] < shame_res[res])   //res刚好对应那一天
            {
                res = i;
            }
        }
    }
    cout << res + 1 << endl;
    return 0;
}

//day18
//压缩字符串(一)
#include <string>
#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param param string字符串
     * @return string字符串
     */
    string compressString(string param)
    {
        string res;
        string st;
        int cnt = 1;
        for (int i = 0; i < param.size(); i++)
        {
            if (st.empty())
            {
                st.push_back(param[i]);
            }
            else if (param[i] == st.back())
            {
                cnt++;
            }
            else if (param[i] != st.back())
            {
                res += st.back();
                if (cnt > 1)
                    res += to_string(cnt);

                cnt = 1;
                st.pop_back();
                st.push_back(param[i]);
            }
        }

        if (!st.empty())
        {
            res += st.back();
            if (cnt > 1)
                res += to_string(cnt);
        }

        return  res;
    }
};

//chika和蜜柑
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    vector<pair<long long, long long>> oranges(n);  //<sour, sweet>
    for (int i = 0; i < n; i++)
    {
        cin >> oranges[i].first;
    }
    for (int i = 0; i < n; i++)
    {
        cin >> oranges[i].second;
    }

    sort(oranges.begin(), oranges.end(),
        [](const pair<long long, long long>& c1, const pair<long long, long long>& c2)
        {
            if (c1.second > c2.second)
            {
                return true;
            }
            else if (c1.second == c2.second)
            {
                return c1.first < c2.first;
            }
            return false;
        });

    long long sweet = 0; long long sour = 0;
    for (int i = 0; i < k; i++)
    {
        sour += oranges[i].first;
        sweet += oranges[i].second;
    }

    cout << sour << " " << sweet << endl;

    return 0;
}

//01背包
#include <vector>
class Solution {
public:

    int knapsack(int V, int n, vector<vector<int> >& vw)
    {
        // vector<vector<int>> dp(n+1,vector<int>(V+1));

        // for(int i = 1; i <= n; i++)
        // {
        //     for(int j = 1; j <= V; j++)
        //     {
        //         dp[i][j] = dp[i-1][j];
        //         if(j - vw[i-1][0] >= 0)
        //         {
        //             dp[i][j] = max(dp[i][j], dp[i-1][j-vw[i-1][0]] + vw[i-1][1]);
        //         }
        //     }
        // }

        vector<int> dp(V + 1);
        for (int i = 1; i <= n; i++)
        {
            for (int j = V; j > 0; j--)
            {
                if (j - vw[i - 1][0] >= 0)
                {
                    dp[j] = max(dp[j], dp[j - vw[i - 1][0]] + vw[i - 1][1]);
                }
            }
        }

        return dp[V];
    }
};

//day 19
//小易的升级之路
#include <iostream>
using namespace std;
long long getGcd(long long a, long long b)
{
    long long tmp = a % b;
    while (tmp)
    {
        a = b;
        b = tmp;
        tmp = a % b;
    }

    return b;
}


int main()
{
    long long n, x;
    cin >> n >> x;
    for (int i = 0; i < n; i++)
    {
        long long a = 0;
        cin >> a;
        if (x >= a)
        {
            x += a;
        }
        else
        {
            x += getGcd(x, a);
        }
    }
    cout << x << endl;
    return 0;
}

//礼物的最大价值
 int maxValue(vector<vector<int> >& grid)
{
    int n = grid.size();
    int m = grid[0].size();
    vector<vector<int>> dp(n, vector<int>(m));
    dp[0][0] = grid[0][0];

    for (int i = 1; i < m; i++)
    {
        dp[0][i] += dp[0][i - 1] + grid[0][i];
    }

    for (int i = 1; i < n; i++)
    {
        dp[i][0] += dp[i - 1][0] + grid[i][0];
    }

    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    return dp[n - 1][m - 1];
}

 //对称之美
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int t = 0;
     cin >> t;
     while (t--)
     {
         int n = 0;
         cin >> n;
         vector<string> strs(n);
         for (int i = 0; i < n; i++)
         {
             cin >> strs[i];
         }

         int left = 0;
         int right = n - 1;
         while (left < right)
         {
             bool flag = false;
             for (int i = 0; i < strs[left].size(); i++)
             {
                 if (strs[right].find(strs[left][i]) != std::string::npos)
                 {
                     flag = true;
                     break;
                 }
             }
             if (!flag)
             {
                 cout << "No" << endl;
                 break;
             }
             left++;
             right--;
         }
         if (left >= right)
         {
             cout << "Yes" << endl;
         }

     }

     return 0;
 }

 //day 20
 //经此一役小红所向无敌
#include <iostream>
 using namespace std;

 int main()
 {
     long long a, h, b, k;
     cin >> a >> h >> b >> k;

     long long res = 0;
     while (h > 0 && k > 0)
     {
         res += (a + b);
         h -= b;
         k -= a;
     }

     if (h > 0)   res += 10 * a;
     else if (k > 0)  res += 10 * b;

     cout << res << endl;
     return 0;
 }

 //连续子数组最大和(ACM版本)
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n = 0;
     cin >> n;

     vector<long long> nums(n);
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }

     vector<long long> dp(n);
     dp[0] = nums[0];
     long long res = dp[0];
     for (int i = 1; i < n; i++)
     {
         dp[i] = max(dp[i - 1] + nums[i], nums[i]);
         res = max(dp[i], res);
     }

     cout << res << endl;

     return 0;
 }

 //非对称之美
#include <iostream>
#include <string>
#include <vector>
#include <set>
 using namespace std;

 //简单贪心
 bool isPalindrome(string str_in)
 {
     int left = 0;
     int right = str_in.size() - 1;
     while (left < right)
     {
         if (str_in[left] != str_in[right])
         {
             return false;
         }
         left++;
         right--;
     }

     return true;
 }

 int main()
 {
     string str_in;
     cin >> str_in;
     set<char> s(str_in.begin(), str_in.end());
     int res = 0;

     if (isPalindrome(str_in))
     {
         if (s.size() != 1)
         {
             res = str_in.size() - 1;
         }
     }
     else
     {
         res = str_in.size();
     }

     cout << res << endl;
     return 0;
 }

 //day 21
 //爱丽丝的人偶
#include <iostream>
 using namespace std;

 int main()
 {
     int n = 0;
     cin >> n;
     int left = 1; int right = n;

     while (left <= right)
     {
         if (left == right)
         {
             cout << left << " ";
         }
         else
         {
             cout << right << " ";
             cout << left << " ";
         }

         left++;
         right--;
     }
     cout << endl;
     return 0;
 }

 //集合
#include <iostream>
#include <set>
 using namespace std;

 int main()
 {
     set<int> s;
     int n, m;
     cin >> n >> m;
     for (int i = 0; i < n + m; i++)
     {
         int num;
         cin >> num;
         s.insert(num);
     }
     for (auto e : s)
     {
         cout << e << " ";
     }
     cout << endl;
     return 0;
 }

 //最长回文子序列
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
 using namespace std;

 int main()
 {
     string s;
     cin >> s;
     int n = s.size();
     vector<vector<int>> dp(n, vector<int>(n));
     for (int j = 0; j < n; j++)
     {
         for (int i = j; i >= 0; i--)
         {
             dp[i][j] = 1;
             if (s[i] == s[j])
             {
                 if (i == j)
                 {
                     dp[i][j] = 1;
                 }
                 else if (i + 1 == j)
                 {
                     dp[i][j] = 2;
                 }
                 else
                 {
                     dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
                 }
             }
             else
             {
                 dp[i][j] = max({ dp[i][j], dp[i + 1][j], dp[i][j - 1] });
             }
         }
     }

     cout << dp[0][n - 1] << endl;
     return 0;
 }

 //day 22
 //添加字符
#include <iostream>
#include <algorithm>
 using namespace std;

 int main()
 {
     string s1, s2;
     cin >> s1 >> s2;
     int same = 0;

     for (int i = 0; i < s2.size(); i++)
     {
         int len = 0;
         int pos = i;
         if (i + s1.size() > s2.size())   //此时s2已超出s1，即使相等也不算
         {
             break;
         }
         for (int j = 0, pos = i; j < s1.size() && pos < s2.size(); j++, pos++)
         {
             if (s1[j] == s2[pos])
             {
                 len++;
             }
         }
         same = max(len, same);
     }

     cout << s1.size() - same << endl;
     return 0;
 }

 //数组变换
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n;
     cin >> n;
     vector<long long> nums(n);

     long long maxnum = 0;
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
         maxnum = max(maxnum, nums[i]);
     }

     bool flag = true;
     for (int i = 0; i < n; i++)
     {
         if (maxnum % nums[i] != 0)
         {
             flag = false;
             break;
         }
     }

     if (!flag)
     {
         cout << "NO";
     }
     else {
         cout << "YES";
     }

     return 0;
 }


 //装箱问题
#include <algorithm>
#include <iostream>
#include <vector>
 using namespace std;

 //认为物品的价值等于它的体积，问题就转换为了01背包
 int main()
 {
     int V, n;
     cin >> V >> n;

     vector<int> volumns(n);
     for (int i = 0; i < n; i++)
     {
         cin >> volumns[i];
     }

     vector<vector<int>> dp(n + 1, vector<int>(V + 1));
     for (int i = 1; i <= n; i++)
     {
         for (int j = 1; j <= V; j++)
         {
             dp[i][j] = dp[i - 1][j];
             if (j - volumns[i - 1] >= 0)
             {
                 dp[i][j] = max(dp[i][j], dp[i - 1][j - volumns[i - 1]] + volumns[i - 1]);
             }
             //cout << dp[i][j] << " ";
         }
         //cout << endl;
     }

     cout << V - dp[n][V] << endl;
     return 0;
 }

 //day 23
 //打怪
#include <iostream>
 using namespace std;

 int main()
 {
     int t;
     cin >> t;
     while (t--)
     {
         int h, a, H, A;
         cin >> h >> a >> H >> A;

         if (A == 0 || a >= H)
         {
             cout << -1 << endl;
             continue;
         }

         int hitTime = H / a + (H % a != 0);     //要打多少次怪
         int dimishHp = (hitTime - 1) * A;       //打死一只扣的血

         int cnt = 0;
         while (h > dimishHp)
         {
             h -= dimishHp;
             cnt++;
         }
         cout << cnt << endl;
     }
 }

 //字符串的分类
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
 using namespace std;

 int main()
 {
     int n = 0;
     cin >> n;
     string prev;
     int cnt = 0;
     set<set<char>> sets;

     for (int i = 0; i < n; i++)
     {
         string s;
         cin >> s;

         set<char> charset(s.begin(), s.end());
         if (sets.count(charset) == 0)
         {
             cnt++;
             sets.insert(charset);
         }
     }

     cout << cnt << endl;
     return 0;
 }

 //城市群数量
#include <queue>
#include <utility>
 int vis[210] = { 0 };
 int row = 0;

 void bfs(vector<vector<int> >& m, int start)
 {
     queue<int> qCities;
     qCities.push(start);
     vis[start] = true;

     while (!qCities.empty())
     {
         int node = qCities.front();
         qCities.pop();
         for (int i = 0; i < row; i++)
         {
             int isArrived = m[node][i];
             if (isArrived == 1 && !vis[i])
             {
                 qCities.push(i);
                 vis[i] = true;
             }
         }
     }
 }

 void dfs(vector<vector<int> >& m, int start)
 {
     vis[start] = true;
     for (int i = 0; i < row; i++)
     {
         int isArrived = m[start][i];
         if (isArrived == 1 && !vis[i])
         {
             dfs(m, i);
         }
     }
 }

 int citys(vector<vector<int> >& m)
 {
     int cnt = 0;
     row = m.size();
     for (int i = 0; i < row; i++)
     {
         if (!vis[i])
         {
             //bfs(m, i);
             dfs(m, i);
             cnt++;
         }
     }

     return cnt;
 }

 //day 24
 //判断是不是平衡二叉树
 int height(TreeNode* pRoot)
 {
     if (pRoot == nullptr)
     {
         return 0;
     }

     return max(height(pRoot->left), height(pRoot->right)) + 1;
 }

 bool IsBalanced_Solution(TreeNode* pRoot)
 {
     if (pRoot == nullptr)
     {
         return true;
     }
     return (abs(height(pRoot->left) - height(pRoot->right)) <= 1
         && IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right));
 }

 //最大子矩阵
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n = 0;
     cin >> n;

     vector<vector<int>> nums(n, vector<int>(n));
     vector<vector<int>> dp(n + 1, vector<int>(n + 1));
     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j < n; j++)
         {
             cin >> nums[i][j];
         }
     }

     for (int i = 1; i <= n; i++)
     {
         for (int j = 1; j <= n; j++)
         {
             dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + nums[i - 1][j - 1];
         }
     }

     //四层for枚举所有子矩阵
     int res = -128;
     for (int x1 = 1; x1 <= n; x1++)
     {
         for (int y1 = 1; y1 <= n; y1++)
         {
             for (int x2 = x1; x2 <= n; x2++)
             {
                 for (int y2 = y1; y2 <= n; y2++)
                 {
                     res = max(res, dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]);
                 }
             }

         }
     }
     cout << res << endl;

     return 0;
 }

 //小葱的01串
#include <iostream>
#include <unordered_map>
 using namespace std;
 //由于刚开始是全白，故仅需关组窗口中0和1数目的个数即可！
 int main()
 {
     int n;
     cin >> n;

     string s;
     cin >> s;

     int hash[2] = { 0 };
     for (int i = 0; i < s.size(); i++)
     {
         hash[s[i] - '0']++;
     }

     int len = n / 2;
     int left = 0;
     int right = 0;
     int cnt = 0;
     int check[2] = { 0 };
     while (right < n)
     {
         if (right - left < len)
         {
             check[s[right] - '0']++;
             hash[s[right] - '0']--;
             right++;
         }
         else
         {
             if (check[0] == hash[0] && check[1] == hash[1])
             {
                 cnt += 2;
             }
             check[s[left] - '0']--;
             hash[s[left] - '0']++;
             left++;
         }
     }

     cout << cnt << endl;
     return 0;
 }
 
 //day25
 //[NOIP2008]笨小猴
#include <algorithm>
#include <iostream>
 using namespace std;

 bool isPrime(int num)
 {
     if (num <= 1)
     {
         return false;
     }

     for (int i = 2; i < num; i++)
     {
         if (num % i == 0)
         {
             return false;
         }
     }

     return true;
 }

 int main()
 {
     int hash[26] = { 0 };
     string s;
     cin >> s;
     int maxn = 0;
     int minn = 101;
     for (int i = 0; i < s.size(); i++)
     {
         hash[tolower(s[i]) - 'a']++;
     }
     for (int i = 0; i < 26; i++)
     {
         maxn = max(maxn, hash[i]);
         if (hash[i] != 0)
         {
             minn = min(minn, hash[i]);
         }
     }

     //cout << maxn << " " << minn << endl;
     if (isPrime(maxn - minn))
     {
         cout << "Lucky Word" << endl << maxn - minn << endl;
     }
     else
     {
         cout << "No Answer" << endl << 0 << endl;
     }

     return 0;
 }

 //主持人调度（一）
 bool hostschedule(vector<vector<int> >& schedule)
 {
     sort(schedule.begin(), schedule.end(), [](vector<int>& v1, vector<int>& v2) {
         return v1[0] < v2[0];
         });

     for (int i = 1; i < schedule.size(); i++)
     {
         if (schedule[i][0] < schedule[i - 1][1])
         {
             return false;
         }
     }

     return true;
 }

 //分割等和子集
#include <algorithm>
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n;
     cin >> n;
     vector<long long> nums(n);
     long long sum = 0;
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
         sum += nums[i];
     }

     if (sum % 2 == 0)
     {
         vector<vector<bool>> dp(n + 1, vector<bool>(sum / 2 + 1, true));
         for (int i = 1; i <= n; i++)
         {
             for (int j = 1; j <= sum / 2; j++)
             {
                 dp[i][j] = dp[i - 1][j];
                 if (j - nums[i - 1] >= 0 && dp[i - 1][j - nums[i - 1]])
                 {
                     dp[i][j] = dp[i - 1][j - nums[i - 1]];
                 }
             }
         }

         if (dp[n][sum / 2])
         {
             cout << "true" << endl;
         }
         else
         {
             cout << "false" << endl;
         }
     }
     else
     {
         cout << "false" << endl;
     }

     return 0;
 }

 //day26
 //小红的ABC
#include <iostream>
#include <string>
 using namespace std;

 int main()
 {
     string str;
     cin >> str;

     int res = 0;
     for (int i = 0; i <= str.size(); i++)
     {
         if (i + 1 < str.size() && str[i] == str[i + 1])
         {
             res = 2;
             break;
         }
         else if (i + 2 < str.size() && str[i] == str[i + 2])
         {
             res = 3;
         }
     }
     cout << (res == 0 ? -1 : res) << endl;
     return 0;
 }

 //不相邻取数
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n = 0;
     cin >> n;
     vector<int> nums(n);
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }
     vector<vector<int>> dp(n, vector<int>(2));

     dp[0][0] = 0;
     dp[0][1] = nums[0];

     for (int i = 1; i < n; i++)
     {
         dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
         dp[i][1] = dp[i - 1][0] + nums[i];
     }

     cout << max(dp[n - 1][0], dp[n - 1][1]);
     return 0;

 }

 //空调遥控
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
 using namespace std;

 //并不是找具体的一个元素
 int binarySearch(vector<int>& nums, int key1, int key2)
 {
     int left = 0;
     int right = nums.size() - 1;
     int res = 0;
     while (left < right)
     {
         int mid = (right - left) / 2 + left;
         if (nums[mid] < key1)
         {
             left = mid + 1;
         }
         else
         {
             right = mid;
         }

     }
     res = left;

     left = 0;
     right = nums.size() - 1;
     while (left < right)
     {
         int mid = (right - left + 1) / 2 + left;
         if (nums[mid] > key2)
         {
             right = mid - 1;
         }
         else
         {
             left = mid;
         }
     }

     //cout <<  res << " -- " << left << endl;
     res = left - res + 1;

     return res;
 }

 int slideWindows(vector<int>& nums, int n, int p)
 {
     int left = 0;
     int right = 0;
     int res = 0;
     while (right < n)
     {
         if (nums[right] - nums[left] <= 2 * p)
         {
             right++;
         }
         else
         {
             res = max(res, right - left);
             left++;
         }
     }
     res = max(res, right - left);

     return res;
 }

 int main()
 {
     int n, p;
     cin >> n >> p;
     vector<int> nums(n);

     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }
     sort(nums.begin(), nums.end());

     int minn = nums[0];
     int maxn = nums[n - 1];
     int res = 0;
     //     for(int K = minn; K <= maxn; K++)
     //     {
     //         //cout << K - p << " " << K + p << " -- ";
     //         res = max(res, binarySearch(nums, K-p, K+p));
     //     }

         //滑动窗口
     res = slideWindows(nums, n, p);

     cout << res << endl;
     return 0;
 }

 //day 27
 //kotori和气球
#include <iostream>
 using namespace std;

 int main()
 {
     long long n, m;
     cin >> n >> m;

     long long res = n;
     while (--m)
     {
         res *= (n - 1);
         res %= 109;
     }
     cout << res << endl;
     return 0;
 }

 //走迷宫
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
 using namespace std;

 int res = 0;
 int dx[4] = { 0,0,1,-1 };
 int dy[4] = { 1,-1,0,0 };
 bool vis[1005][1005];
 struct info
 {
     int x; int y; int step;
 };

 int main()
 {
     int n, m;
     cin >> n >> m;
     int xs, ys, xt, yt;
     cin >> xs >> ys >> xt >> yt;

     vector<vector<char>> maze(n + 1, vector<char>(m + 1));
     for (int i = 1; i <= n; i++)
     {
         for (int j = 1; j <= m; j++)
         {
             cin >> maze[i][j];
         }
     }

     queue<info> q;
     q.push({ xs,ys,0 });
     vis[xs][ys] = true;
     while (!q.empty())
     {
         int a = q.front().x;
         int b = q.front().y;
         int s = q.front().step;
         q.pop();
         if (a == xt && b == yt)
         {
             res = max(res, s);
             continue;
         }

         for (int i = 0; i < 4; i++)
         {
             int x = a + dx[i];
             int y = b + dy[i];
             //cout << x << " " << y << endl;
             if (x >= 1 && x <= n && y >= 1 && y <= m && maze[x][y] == '.' && !vis[x][y])
             {

                 q.push({ x,y,s + 1 });
                 vis[x][y] = true;
             }
         }
     }

     cout << (res == 0 ? -1 : res) << endl;
     return 0;
 }

 //主持人调度（二）
 int minmumNumberOfHost(int n, vector<vector<int> >& startEnd)
 {
     sort(startEnd.begin(), startEnd.end(), [](vector<int>& v1, vector<int>& v2) {
         return v1[0] < v2[0];
         });

     priority_queue<int, vector<int>, greater<int>> smallHeap;
     smallHeap.push(startEnd[0][1]);
     int cnt = 1;
     for (int i = 1; i < n; i++)
     {
         if (startEnd[i][0] < smallHeap.top())
         {
             cnt++;
         }
         else
         {
             smallHeap.pop();
         }
         smallHeap.push(startEnd[i][1]);
     }

     return cnt;
 }

 //day 28
 //游游的重组偶数
#include <iostream>
#include <string>
 using namespace std;

 int main()
 {
     int q;
     cin >> q;
     while (q--)
     {
         string s;
         cin >> s;
         string res;
         char evenchar = -1;
         string zeros;
         bool flag = false;
         for (auto e : s)
         {
             if ((e - '0') % 2 == 0 && e != '0' && evenchar == -1)
             {
                 evenchar = e;
                 flag = true;
             }
             else if (e == '0')
             {
                 zeros += e;
                 flag = true;
             }
             else
             {
                 res += e;
             }
         }

         if (!flag)
         {
             cout << "-1";
         }
         else
         {
             if (evenchar == -1)
             {
                 res += zeros;
             }
             else
             {
                 res += evenchar + zeros;
             }
             cout << (std::stoi(res));
         }
         cout << endl;
     }

     return 0;
 }

 //体操队形
#include <iostream>
#include <vector>
 using namespace std;

 int res = 0;
 int n;
 int vis[15] = { 0 };

 void dfs(vector<int>& nums, int curPos)
 {
     if (curPos == nums.size())
     {
         res++;
         return;
     }

     for (int i = 1; i <= n; i++)
     {
         if (vis[i] == 0)
         {
             if (vis[nums[i]] == 1 && nums[i] != i)      //剪枝
             {
                 break;
             }

             if (i == nums[i] || vis[nums[i]] == 0)
             {
                 vis[i] = 1;
                 dfs(nums, curPos + 1);
                 vis[i] = 0;
             }
         }
     }
 }

 int main()
 {
     cin >> n;
     vector<int> nums(n + 1);

     for (int i = 1; i <= n; i++)
     {
         cin >> nums[i];
     }

     dfs(nums, 1);
     cout << res << endl;

     return 0;
 }

 //二叉树中的最大路径和
   //向上返回的是左右子树的最大值加上根节点的值（继续遍历）
    //而更新res的有几种情况：左右子树的和加上根节点的值（搜索答案）、仅左+根、仅右+根、仅根
 int res = -1001;
 int dfs(TreeNode* root)
 {
     if (root == nullptr)
     {
         return 0;
     }

     int leftSum = dfs(root->left);
     int rightSum = dfs(root->right);

     res = max({ res, leftSum + rightSum + root->val, leftSum + root->val, +rightSum + root->val, root->val });
     return max(leftSum, rightSum) + root->val;
 }

 int maxPathSum(TreeNode* root)
 {
     dfs(root);

     return res;
 }

 //day 29
 //排序子序列
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n;
     cin >> n;
     vector<int> nums(n);
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }

     int i = 0;
     int cnt = 0;
     while (i < n)
     {
         if (i == n - 1)
         {
             cnt++;
             break;
         }

         if (nums[i] > nums[i + 1])
         {
             while (i + 1 < n && nums[i] >= nums[i + 1])
             {
                 i++;
             }
             cnt++;
         }
         else if (nums[i] < nums[i + 1])
         {
             while (i + 1 < n && nums[i] <= nums[i + 1])
             {
                 i++;
             }
             cnt++;
         }
         else
         {
             while (i + 1 < n && nums[i] == nums[i + 1])
             {
                 i++;
             }
         }
         i++;
     }

     cout << cnt << endl;
     return 0;
 }
 

 //消减整数
#include <iostream>
 using namespace std;

 int main()
 {
     int T;
     cin >> T;
     while (T--)
     {
         int n;
         cin >> n;
         int cnt = 1;
         int cur = 1;
         n -= cur;
         while (n > 0)
         {
             if (n % (2 * cur) == 0)
             {
                 cur *= 2;
             }
             n -= cur;
             cnt++;
         }
         cout << cnt << endl;
     }


     return 0;
 }


 //最长上升子序列(二)
 int binarySearch(vector<int>& a, int key)
 {
     int left = 0;
     int right = a.size() - 1;

     while (left < right)
     {
         int mid = (right - left) / 2 + left;
         if (a[mid] < key)
         {
             left = mid + 1;
         }
         else
         {
             right = mid;
         }
     }

     return left;
 }

 int LIS(vector<int>& a)
 {
     int n = a.size();
     vector<int> dp;
     int res = 0;
     for (int i = 0; i < n; i++)
     {
         int index = binarySearch(dp, a[i]);
         cout << index << " ";
         if (index >= dp.size() || a[i] > dp.back())
         {
             dp.push_back(a[i]);
         }
         else
         {
             dp[index] = a[i];
         }
     }

     return dp.size();
 }

 //day 30
 //爱吃素
#include <cmath>
#include <iostream>
 using namespace std;

 bool isPrime(unsigned long long n)
 {
     if (n < 2)
     {
         return false;
     }
     for (int i = 2; i <= sqrt(n); i++)
     {
         if (n % i == 0)
         {
             return false;
         }
     }

     return true;
 }

 int main()
 {
     int t;
     cin >> t;
     while (t--)
     {
         unsigned long long a, b;
         cin >> a >> b;
         if (a > 1 && b > 1)
         {
             cout << "NO" << endl;
         }
         else
         {
             if ((a == 1 && isPrime(b)) || (b == 1 && isPrime(a)))
             {
                 cout << "YES" << endl;
             }
             else
             {
                 cout << "NO" << endl;
             }
         }
     }

 }

 //相差不超过k的最多数
 int main()
 {
     int n, k;
     cin >> n >> k;
     vector<int> nums(n);
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }

     sort(nums.begin(), nums.end());

     int left = 0;
     int right = 0;
     int res = 0;

     while (right < n)
     {
         if (nums[right] - nums[left] <= k)
         {
             right++;
         }
         else
         {
             res = max(res, right - left);
             left++;
         }
     }
     res = max(res, right - left);

     cout << res << endl;
     return 0;
 }

 //最长公共子序列(一)
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n, m;
     cin >> n >> m;

     string s1, s2;
     cin >> s1 >> s2;

     vector<vector<int>> dp(n + 1, vector<int>(m + 1));
     int res = 0;
     for (int i = 1; i <= n; i++)
     {
         for (int j = 1; j <= n; j++)
         {
             if (s1[i - 1] == s2[j - 1])
             {
                 dp[i][j] = dp[i - 1][j - 1] + 1;
             }
             else
             {
                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
             }
             res = max(res, dp[i][j]);
         }
     }

     cout << res << endl;
     return 0;
 }

 //day 31
 //小红的口罩
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
 using namespace std;

 int main()
 {
     int n, k;
     cin >> n >> k;

     priority_queue<long long, vector<long long>, greater<long long>> unc_vals;
     for (int i = 0; i < n; i++)
     {
         long long a = 0;
         cin >> a;
         unc_vals.push(a);
     }

     long long unc_val = 0;
     int res = -1;
     while (unc_val < k)
     {
         long long v = unc_vals.top();
         //cout << v << " ";
         unc_vals.pop();
         unc_val += v;
         unc_vals.push(v * 2);
         res++;
     }

     cout << res << endl;

     return 0;
 }

 //春游
#include <iostream>
#include <algorithm>
 using namespace std;
 int main()
 {
     int T;
     cin >> T;

     while (T--)
     {
         long long n, a, b;
         cin >> n >> a >> b;
         if (n <= 2)
         {
             cout << min(a, b) << endl;
             continue;
         }

         long long res = 0;
         if (3 * a < 2 * b)
         {
             res = n / 2 * a;
             if (n % 2 == 1)
             {
                 res += min({ a, b, b - a });
             }
         }
         else
         {
             res = n / 3 * b;
             if (n % 3 == 2)
             {
                 res += min({ a, b, 3 * a - b });
             }
             else if (n % 3 == 1)
             {
                 res += min({ a, b, 2 * a - b });
             }
         }

         cout << res << endl;
     }
     return 0;
 }

 //数位染色
#include <iostream>
#include <algorithm>
#include <string>
 using namespace std;

 //1. 排序  //2. 滑动窗口
 int main()
 {
     string s;
     cin >> s;

     sort(s.begin(), s.end());
     int sum = 0;
     for (int i = 0; i < s.size(); i++)
     {
         sum += s[i] - '0';
     }

     int left = 0, right = 0;
     bool flag = false;
     int tmpsum = 0;
     while (right < s.size() && sum % 2 == 0)  //sum一定是偶数
     {
         if (tmpsum < sum / 2)
         {
             tmpsum += (s[right] - '0');
             right++;
         }
         else if (tmpsum == sum / 2)
         {
             flag = true;
             break;
         }
         else if (tmpsum > sum / 2)
         {
             tmpsum -= (s[left] - '0');
             left++;
         }
         //cout << tmpsum << " ";
     }

     if (flag) cout << "Yes" << endl;
     else cout << "No" << endl;
     return 0;
 }

 //day 32
 //素数回文
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
 using namespace std;

 bool IsPrime(long long n)
 {
     for (int i = 2; i <= sqrt(n); i++)
     {
         if (n % i == 0)
         {
             return false;
         }
     }

     return true;
 }

 int main()
 {
     string s;
     cin >> s;

     string tmps = s.substr(0, s.size() - 1);
     reverse(tmps.begin(), tmps.end());
     s += tmps;

     if (IsPrime(stol(s)))
     {
         cout << "prime" << endl;
     }
     else
     {
         cout << "noprime" << endl;
     }

     return 0;
 }

 //活动安排
#include <algorithm>
#include <iostream>
#include <utility>
#include <queue>
 using namespace std;

 using pii = pair<int, int>;
 int main()
 {
     int n;
     cin >> n;
     vector<priority_queue<int, vector<int>, greater<int>>> vq(1000005);
     int maxn = 0;
     for (int i = 0; i < n; i++)
     {
         int a, b;
         cin >> a >> b;

         maxn = max(a, maxn);
         vq[a].push(b);
     }

     int res = 0;
     int i = 0;
     while (i <= maxn)
     {
         if (!vq[i].empty())
         {
             i = vq[i].top();
             res++;
         }
         else
         {
             i++;
         }
     }

     cout << res << endl;
     return 0;
 }

 //合唱团

 //day 33
 //跳台阶扩展问题
#include <iostream>
#include <ostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n = 0;
     cin >> n;

     vector<int> dp(n + 1);
     dp[1] = 1; dp[2] = 2;
     for (int i = 3; i <= n; i++)
     {
         dp[i] = 1;
         for (int j = 1; j < i; j++)
         {
             dp[i] += dp[j];
         }
     }

     cout << dp[n] << endl;
     return 0;
 }

//包含不超过两种字符的最长子串
#include <algorithm>
#include <iostream>
#include <unordered_map>
 using namespace std;
 //出窗口的是right往前走，走到不能走那一个字符
 int main()
 {
     string s;
     cin >> s;

     int left = 0;
     int right = 0;
     int cnt = 1;
     int len = 0;
     unordered_map<char, int> hash;
     hash[s[left]] = left;

     while (right < s.size())
     {

         if (hash.count(s[right]) == 0)
         {
             if (cnt == 0)    //已达最大字符限制
             {
                 len = max(len, right - left);

                 //找要出哪个字符
                 int tmpi = right - 1;
                 while (tmpi - 1 >= 0 && s[tmpi] == s[tmpi - 1])
                 {
                     tmpi--;
                 }

                 left = hash[s[tmpi - 1]] + 1;
                 hash.erase(s[tmpi - 1]);
                 cnt++;
             }
             hash[s[right]] = right;
             cnt--;
         }
         else
         {
             hash[s[right]] = right;     //更新，保证下标是最靠右的，方便出窗口
         }
         right++;
     }
     len = max(len, right - left);

     cout << len << endl;
     return 0;
 }

//字符串的排列
#include <set>
#include <string>
#include <vector>
 class Solution {
 public:
     string aux;
     vector<string> res;
     set<string> s;
     int n = 0;
     vector<bool> vis;
     void dfs(int cnt, string& str)
     {
         if (cnt == n)
         {
             if (s.count(aux) == 0)
             {
                 s.insert(aux);
                 res.push_back(aux);
             }
             return;
         }

         for (int i = 0; i < n; i++)
         {
             if (!vis[i])
             {
                 vis[i] = true;
                 aux.push_back(str[i]);
                 dfs(cnt + 1, str);
                 vis[i] = false;
                 aux.pop_back();
             }
         }
     }
     vector<string> Permutation(string str)
     {
         n = str.size();
         vis.resize(n);
         dfs(0, str);
         return res;
     }
 };

 // day 34
 //ISBN号码
#include <iostream>
#include <ostream>
 using namespace std;

 int main()
 {
     string s;
     cin >> s;

     long long sum = 0;
     int plus = 1;
     for (int i = 0; i < s.size() - 1; i++)
     {
         if (s[i] >= '0' && s[i] <= '9')
         {
             sum += (s[i] - '0') * plus;
             //cout << sum << " ";
             plus++;
         }
     }

     sum = sum % 11;
     char code;
     if (sum == 10)
     {
         code = 'X';
     }
     else
     {
         code = sum % 11 + '0';
     }
     if (s.back() == code)
     {
         cout << "Right" << endl;
     }
     else
     {
         s.back() = code;
         cout << s << endl;
     }

     return 0;
 }

 //kotori和迷宫
#include <iostream>
#include <queue>
#include <vector>
 using namespace std;

 int res_step = 0x3f3f3f3f;
 int res_cnt = 0;

 struct info
 {
     int x;
     int y;
     int step;
 };

 int main()
 {
     int dx[] = { 0,0,1,-1 };
     int dy[] = { 1,-1,0,0 };

     int n, m;
     cin >> n >> m;
     int sx = 0, sy = 0;
     vector<vector<char>> maze(n, vector<char>(m));
     vector<vector<bool>> vis(n, vector<bool>(m));
     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j < m; j++)
         {
             cin >> maze[i][j];
             if (maze[i][j] == 'k')
             {
                 sx = i; sy = j;
             }
         }
     }

     queue<info> q;
     q.push({ sx,sy,0 });
     vis[sx][sy] = true;

     while (!q.empty())
     {
         auto [a, b, step] = q.front();
         q.pop();

         if (maze[a][b] == 'e')
         {
             res_cnt++;
             res_step = min(step, res_step);
             continue;
         }
         for (int i = 0; i < 4; i++)
         {
             int x = a + dx[i];
             int y = b + dy[i];
             if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && maze[x][y] != '*')
             {
                 q.push({ x,y,step + 1 });
                 vis[x][y] = true;
             }
         }
     }

     if (res_cnt == 0)
     {
         cout << -1 << endl;
     }
     else
     {
         cout << res_cnt << " " << res_step << endl;
     }

     return 0;
 }

 //矩阵最长递增路径


 //day 35
 //提取不重复的整数
#include <algorithm>
#include <iostream>
#include <unordered_set>
 using namespace std;

 int main()
 {
     string str;
     cin >> str;

     string res;
     unordered_set<char> nums;
     for (int i = str.size() - 1; i >= 0; i--)
     {
         if (nums.count(str[i]) == 0)
         {
             res += str[i];
             nums.insert(str[i]);
         }
     }
     cout << res << endl;

     return 0;
 }

 //哈夫曼编码
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
 using namespace std;

 //采用 边构建树，边计算权值的方式
 int main()
 {
     int n;
     cin >> n;
     priority_queue<long long, vector<long long>, greater<long long>> smallHeap;
     for (int i = 0; i < n; i++)
     {
         long long a;
         cin >> a;
         smallHeap.push(a);
     }

     long long sum = 0;
     while (smallHeap.size() > 1)
     {
         long long tmp = 0;
         tmp += smallHeap.top();
         smallHeap.pop();

         tmp += smallHeap.top();
         smallHeap.pop();

         smallHeap.push(tmp);
         sum += tmp;
     }

     cout << sum << endl;
     return 0;
 }

 //abb
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n;
     cin >> n;

     string s;
     cin >> s;

     vector<long long> dp(n);  //以i为结尾的子序列，有多少abb形式
     long long sum = 0;
     long long f[26] = { 0 };    //区间内有多少_x
     long long g[26] = { 0 };    //区间内有多少x

     //注意更新dp表和哈希表的顺序！
     for (int i = 0; i < n; i++)
     {
         dp[i] = f[s[i] - 'a'];
         sum += dp[i];
         f[s[i] - 'a'] += (i - g[s[i] - 'a'] < 0 ? 0 : i - g[s[i] - 'a']);
         g[s[i] - 'a']++;
     }

     cout << sum << endl;
     return 0;
 }

 //day 37
 // 旋转字符串
 bool solve(string A, string B)
 {
     if (A == B)
     {
         return true;
     }

     for (int i = 1; i <= A.size(); i++)
     {
         string left = A.substr(0, i);
         string right = A.substr(i);

         if (right + left == B)
         {
             return true;
         }
     }

     return false;
 }
 
 //合并k个已排序的链表
 ListNode* mergeKLists(vector<ListNode*>& lists)
 {
     if (lists.size() == 0)
     {
         return nullptr;
     }

     vector<int> nums;
     for (int i = 0; i < lists.size(); i++)
     {
         ListNode* mov = lists[i];
         while (mov != nullptr)
         {
             nums.push_back(mov->val);
             mov = mov->next;
         }
     }

     if (nums.size() == 0)
     {
         return nullptr;
     }
     sort(nums.begin(), nums.end());
     ListNode* head = new ListNode(nums[0]);
     ListNode* cur = head;
     for (int i = 1; i < nums.size(); i++)
     {
         ListNode* newnode = new ListNode(nums[i]);
         cur->next = newnode;
         cur = cur->next;
     }
     return head;
 }

 //滑雪


 //day 38
 //天使果冻
#include <iostream>
#include <vector>
#include <algorithm>
 using namespace std;

 int main()
 {
     int n;
     cin >> n;
     vector<int> nums(n);
     vector<int> leftSecondMax(n);
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }

     int leftMax = nums[0];
     for (int i = 1; i < n; i++)
     {
         if (nums[i] >= leftMax)
         {
             leftSecondMax[i] = leftMax;
             leftMax = nums[i];
         }
         else if (nums[i] < leftMax && nums[i] >= leftSecondMax[i - 1])
         {
             leftSecondMax[i] = nums[i];
         }
         else        //虽说是值不变，但需要填进dp表中！
         {
             leftSecondMax[i] = leftSecondMax[i - 1];
         }
     }
     //     for(int i = 0; i < n; i++)
     //     {
     //         cout << leftSecondMax[i] << " ";
     //     }
     //     cout << endl;
     int q = 0;
     cin >> q;
     while (q--)
     {
         int x;
         cin >> x;
         cout << leftSecondMax[x - 1] << endl;
     }

     return 0;
 }

 //dd爱旋转
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n;
     cin >> n;
     vector<vector<int>> matrix(n, vector<int>(n));
     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j < n; j++)
         {
             cin >> matrix[i][j];
         }
     }

     int q;
     cin >> q;
     int row = 0, col = 0;
     for (int i = 0; i < q; i++)
     {
         int x = 0;
         cin >> x;
         if (x == 1)
         {
             row++;
             col++;
         }
         else
         {
             row++;
         }
     }

     row %= 2;
     col %= 2;
     while (row--)
     {
         for (int i = 0, j = n - 1; i < j; i++, j--)
         {
             swap(matrix[i], matrix[j]);
         }
     }
     while (col--)
     {
         for (int i = 0, j = n - 1; i < j; i++, j--)
         {
             for (int k = 0; k < n; k++)
             {
                 swap(matrix[k][i], matrix[k][j]);
             }
         }
     }

     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j < n; j++)
         {
             cout << matrix[i][j] << " ";
         }
         cout << endl;
     }
     return 0;
 }


 //小红取数
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n, k;
     cin >> n >> k;
     vector<long long> nums(n);
     vector<vector<long long>> dp(n + 1, vector<long long>(k, 0));
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }

     for (int i = 1; i < k; i++)
     {
         dp[0][i] = -0x3f3f3f3f3f3f3f3f;
     }

     for (int i = 1; i <= n; i++)
     {
         for (int j = 0; j < k; j++)
         {
             dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - nums[i - 1] % k + k) % k] + nums[i - 1]);
         }
     }

     // for(int i = 1; i <= n; i++)
     // {
     //     for(int j = 0; j < k; j++)
     //     {
     //         cout << dp[i][j] << " ";
     //     }
     //     cout << endl;
     // }

     cout << (dp[n][0] <= 0 ? -1 : dp[n][0]) << endl;
     return 0;
 }

 //day 39
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
 using namespace std;

 //完全背包问题！
 int main()
 {
     int n;
     cin >> n;

     // vector<vector<int>> dp(n+1, vector<int>(n+1, 0x3f3f3f3f));
     // dp[0][0] = 0;
     // for(int i = 0; i <= n; i++)
     // {
     //     dp[i][0] = 0;
     // }

     // for(int i = 1; i * i<= n; i++)
     // {
     //     for(int j = 1; j <= n; j++)
     //     {
     //         dp[i][j] = dp[i-1][j];
     //         if(j >= i*i)
     //         {
     //             dp[i][j] = min(dp[i-1][j], dp[i][j - i * i] + 1);                 
     //         }
     //     }
     // }
     // cout << dp[sqrt(n)][n] << endl;

     vector<int> dp(n + 1, 0x3f3f3f3f);
     dp[0] = 0;
     for (int i = 1; i <= n; i++)
     {
         for (int j = 1; j <= n; j++)
         {
             if (j >= i * i)
             {
                 dp[j] = min(dp[j], dp[j - i * i] + 1);
             }
         }
     }

     cout << dp[n] << endl;
     return 0;
 }

 //day 40
 //游游的字母串
#include <iostream>
 using namespace std;

 int main()
 {
     string s;
     cin >> s;

     int res = 0x3f3f3f3f;
     for (char cur = 'a'; cur <= 'z'; cur++)
     {
         int cnt = 0;
         for (int i = 0; i < s.size(); i++)
         {
             if (s[i] > cur)
             {
                 cnt += min((s[i] - cur), (cur - s[i] + 26) % 26);
             }
             else
             {
                 cnt += min((cur - s[i]), (s[i] - cur + 26) % 26);
             }
         }

         res = min(res, cnt);
     }

     cout << res << endl;
 }

 //体育课测验(二)
 vector<int> findOrder(int numProject, vector<vector<int> >& groups)
 {
     vector<vector<int>> graph(numProject);
     vector<int> degree(numProject);

     for (int i = 0; i < groups.size(); i++)
     {
         int from = groups[i][1];
         int to = groups[i][0];

         graph[from].push_back(to);
         degree[to]++;
     }

     vector<int> res;
     queue<int> qProject;
     for (int i = 0; i < numProject; i++)
     {
         if (degree[i] == 0)
         {
             qProject.push(i);
             res.push_back(i);
         }
     }

     while (!qProject.empty())
     {
         int cur = qProject.front();
         qProject.pop();
         for (int i = 0; i < graph[cur].size(); i++)
         {
             int to = graph[cur][i];
             if (--degree[to] == 0)
             {
                 qProject.push(to);
                 res.push_back(to);
             }
         }
     }

     if (res.size() != numProject) 
     {
         return {};
     }
     else 
     {
         return res;
     }
 }

 //合唱队形
#include <algorithm>
#include <iostream>
#include <vector>
 using namespace std;

 //正难则反
 //两个dp：最长递增子序列和最长递减子序列(x)
 //两个dp：以i为结尾的最长递增子序列和以i为开头的最长递增子序列(√)
 int main()
 {
     int n;
     cin >> n;
     vector<int> nums(n);
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }

     vector<int> dpUp(n, 1);
     vector<int> dpDown(n, 1);

     for (int i = 1; i < n; i++)
     {
         for (int j = i - 1; j >= 0; j--)
         {
             if (nums[i] > nums[j])
             {
                 dpUp[i] = max(dpUp[i], dpUp[j] + 1);
             }
         }
     }

     for (int i = n - 2; i >= 0; i--)
     {
         for (int j = i + 1; j < n; j++)
         {
             if (nums[i] > nums[j])
             {
                 dpDown[i] = max(dpDown[i], dpDown[j] + 1);
             }
         }
     }

     int len = 0;
     for (int i = 0; i < n; i++)
     {
         len = max(len, dpUp[i] + dpDown[i] - 1);
     }
     cout << n - len << endl;
     return 0;
 }

 //day 41
 //棋子翻转
 vector<vector<int> > flipChess(vector<vector<int> >& A, vector<vector<int> >& f)
 {
     int dx[4] = { 1,-1,0,0 };
     int dy[4] = { 0,0,1,-1 };
     int n = A.size();
     int m = A[0].size();
     for (int i = 0; i < f.size(); i++)
     {
         for (int j = 0; j < 4; j++)
         {
             int x = f[i][0] - 1 + dx[j];
             int y = f[i][1] - 1 + dy[j];
             if (x >= 0 && x < n && y >= 0 && y < m)
             {
                 if (A[x][y] == 1)
                 {
                     A[x][y] = 0;
                 }
                 else
                 {
                     A[x][y] = 1;
                 }
             }
         }
     }
     return A;
 }

 //宵暗的妖怪
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n;
     cin >> n;
     vector<long long> vals(n);
     for (int i = 0; i < n; i++)
     {
         cin >> vals[i];
     }

     vector<long long> dp(n);
     dp[2] = vals[1];
     for (int i = 3; i < n; i++)
     {
         dp[i] = max(dp[i - 1], vals[i - 1] + dp[i - 3]);
     }

     cout << dp[n - 1] << endl;
     return 0;
 }

 //过桥
#include <iostream>
#include <vector>
 using namespace std;
 int bfs(vector<int>& a)
 {
     int left = 1, right = 1;
     int res = 0;

     while (left <= right)
     {
         res++;
         int next = right;
         for (int i = left; i <= right; i++)
         {
             next = max(next, a[i] + i);
             if (next >= a.size() - 1)
             {
                 return res;
             }
         }

         left = right + 1;
         right = next;
     }
     return -1;
 }

 int main()
 {
     int n;
     cin >> n;
     vector<int> a(n + 1);
     for (int i = 1; i <= n; i++)
     {
         cin >> a[i];
     }

     cout << bfs(a) << endl;
     return 0;
 }

 //day 42
 //最大差值
 int getDis(vector<int>& A, int n)
 {
     vector<int> rightMax(n, INT_MIN);
     vector<int> leftMin(n, INT_MAX);
     leftMin[0] = A[0];
     for (int i = 1; i < n; i++)
     {
         leftMin[i] = min(leftMin[i - 1], A[i]);
     }

     rightMax[n - 1] = A[n - 1];
     for (int i = n - 2; i >= 0; i--)
     {
         rightMax[i] = max(rightMax[i + 1], A[i]);
     }


     int res = 0;
     for (int i = 0; i < n; i++)
     {
         res = max(res, rightMax[i] - leftMin[i]);
     }

     return res;
 }

 //兑换零钱
#include <iostream>
#include <vector>

 using namespace std;
 //不同的张数其实也就对应着不同的种数
 int main()
 {
     int n, aim = 0;
     cin >> n >> aim;

     vector<int> faceVals(n);
     vector<int> dp(aim + 1, 0x3f3f3f3f);
     dp[0] = 0;
     for (int i = 0; i < n; i++)
     {
         cin >> faceVals[i];
     }

     for (int i = 0; i < n; i++)
     {
         for (int j = 1; j <= aim; j++)
         {
             if (j >= faceVals[i])
             {
                 dp[j] = min(dp[j], dp[j - faceVals[i]] + 1);
             }
         }
     }

     cout << (dp[aim] == 0x3f3f3f3f ? -1 : dp[aim]) << endl;

     return 0;
 }

 //小红的子串
#include <iostream>
#include <vector>

 using namespace std;

 int main()
 {
     int n, l, r;
     cin >> n >> l >> r;
     vector<long long> prefix(r + 1, 0);
     string s;
     cin >> s;
     //滑动窗口求字符种数在[1,1]~[1,r]之间的子串个数
     //更新前缀和数组时，种数的计算刚好是right - left + 1
     for (int i = 1; i <= r; i++)
     {
         int hash[26] = { 0 };
         int left = 0;
         int right = 0;
         int cnt = 0;
         while (right < n)
         {
             if (hash[s[right] - 'a'] == 0 && cnt < i)
             {
                 hash[s[right] - 'a']++;
                 cnt++;
                 prefix[i] += right - left + 1;
                 right++;
             }
             else if (hash[s[right] - 'a'] != 0 && cnt <= i)
             {
                 hash[s[right] - 'a']++;
                 prefix[i] += right - left + 1;
                 right++;
             }
             else
             {
                 if (--hash[s[left] - 'a'] == 0)
                 {
                     cnt--;
                 }
                 left++;
             }
         }
     }
     //     for(int i = 1; i <= r; i++)
     //     {
     //         cout << prefix[i] << " ";
     //     }
     //     cout << endl;

     cout << prefix[r] - prefix[l - 1] << endl;
     return 0;
 }

 //day 43
 //kotori和抽卡(二)
#include <cmath>
#include <cstdio>
#include <iostream>
 using namespace std;

 double C(int n, int m)
 {
     double res = 1;
     for (int i = 0; i < m; i++)
     {
         res *= n;
         n--;
     }

     double tmp = 1;
     for (int i = 1; i <= m; i++)
     {
         tmp *= i;
     }

     return res / tmp;
 }
 int main()
 {
     int n, m;
     cin >> n >> m;


     printf("%.4lf", C(n, m) * pow(0.8, m) * pow(0.2, n - m));

     return 0;
 }

 //ruby和薯条
#include <algorithm>
#include <iostream>
#include <vector>
 using namespace std;

 long long binarySearchLeft(vector<long long>& nums, int key)
 {
     int left = 0;
     int right = nums.size() - 1;

     while (left < right)
     {
         int mid = (right - left) / 2 + left;
         if (nums[mid] < key)
         {
             left = mid + 1;
         }
         else
         {
             right = mid;
         }
     }

     if (nums[left] < key)
     {
         return -1;
     }
     return left;
 }

 long long binarySearchRight(vector<long long>& nums, int key)
 {
     int left = 0;
     int right = nums.size() - 1;

     while (left < right)
     {
         int mid = (right - left + 1) / 2 + left;
         if (nums[mid] > key)
         {
             right = mid - 1;
         }
         else
         {
             left = mid;
         }
     }

     if (nums[left] > key)
     {
         return -1;
     }
     return left;
 }

 int main()
 {
     long long n, l, r;
     cin >> n >> l >> r;

     vector<long long> nums(n);
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }
     sort(nums.begin(), nums.end());

     long long cnt = 0;
     for (int i = 0; i < n; i++)
     {
         long long lres = binarySearchLeft(nums, nums[i] + l);
         long long rres = binarySearchRight(nums, nums[i] + r);

         //cout << i << " " << lres << " " << rres << endl;
         if (lres != -1 && rres != -1)
         {
             cnt += (rres - lres >= 0) ? (rres - lres + 1) : 0;
         }
     }

     cout << cnt << endl;
     return 0;
 }

 //循环汉诺塔
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n = 0;
     cin >> n;
     // vector<vector<long long>> dp(n+1, vector<long long>(2));
     // dp[1][0] = 1;
     // dp[1][1] = 2;
     long long dp0 = 1;
     long long dp1 = 2;

     for (int i = 2; i <= n; i++)
     {
         // dp[i][0] = (dp[i-1][1] + 1 + dp[i-1][1]) % 1000000007;
         // dp[i][1] = (dp[i-1][1] + 1 + dp[i-1][0] + 1 + dp[i-1][1]) % 1000000007;
         int prev = dp0;
         dp0 = (dp1 + 1 + dp1) % 1000000007;
         dp1 = (dp1 + 1 + prev + 1 + dp1) % 1000000007;
     }

     //cout << dp[n][0] << " " << dp[n][1] << endl;
     cout << dp0 << " " << dp1 << endl;
 }


//day 44
 //最小差值
#include <algorithm>
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n;
     cin >> n;
     vector<int> nums(n);
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }

     sort(nums.begin(), nums.end());
     int res = 0x3f3f3f3f;
     for (int i = 1; i < n - 1; i++)
     {
         res = min({ res, nums[i] - nums[i - 1], nums[i + 1] - nums[i] });
     }


     cout << res << endl;
     return 0;
 }


 //kotori和素因子
#include <algorithm>
#include <cmath>
#include <iostream>
#include <unordered_set>
#include <vector>
 using namespace std;

 int res = 0x3f3f3f3f;
 int n;
 unordered_set<int> s;

 //每层固定一个数，而不用for遍历整个数组
 bool isPrime(int num)
 {
     if (num < 2)
     {
         return false;
     }
     for (int i = 2; i <= sqrt(num); i++)
     {
         if (num % i == 0)
         {
             return false;
         }
     }

     return true;
 }

 void dfs(vector<int>& nums, int sum, int i)
 {
     if (i == n)
     {
         //cout << start << " " << n << " " << sum << endl;
         res = min(res, sum);
         return;
     }

     //bool flag = false;       会误判？
     for (int j = 1; j <= nums[i]; j++)
     {
         if (nums[i] % j == 0 && isPrime(j) && s.count(j) == 0)
         {
             //cout << j << endl;
             //flag = true;
             s.insert(j);
             dfs(nums, sum + j, i + 1);
             s.erase(j);
         }
     }

     // if(!flag)
     // {
     //     res = -1;
     // }
 }

 int main()
 {
     cin >> n;
     vector<int> nums(n);

     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }
     dfs(nums, 0, 0);

     cout << (res == 0x3f3f3f3f ? -1 : res) << endl;
     return 0;
 }

 //dd爱科学1.0
#include <iostream>
#include <string>
#include <vector>
 using namespace std;

 int binarySearch(vector<int>& lens, int num)
 {
     int left = 0;
     int right = lens.size() - 1;
     while (left < right)
     {
         int mid = (right - left) / 2 + left;
         if (lens[mid] <= num)
         {
             left = mid + 1;
         }
         else
         {
             right = mid;
         }
     }

     return left;
 }

 int main()
 {
     int n;
     cin >> n;
     string s;
     cin >> s;

     vector<int> lens;
     for (int i = 0; i < n; i++)
     {
         if (lens.empty() || s[i] >= lens.back())
         {
             lens.push_back(s[i]);
         }
         else
         {
             lens[binarySearch(lens, s[i])] = s[i];
         }
     }

     cout << n - lens.size() << endl;
     return 0;
 }

 //day 45
 //kanan和高音
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n;
     cin >> n;
     vector<int> nums(n);
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
     }

     int left = 0;
     int right = 1;
     int res = 0;
     while (right < n)
     {
         if (nums[right] - nums[right - 1] <= 8)
         {
             right++;
         }
         else
         {
             res = max(res, right - left);
             left = right;
             right++;
         }
     }
     res = max(res, right - left);

     cout << res << endl;
     return 0;
 }

 //拜访
 int dx[4] = { 1,-1,0,0 };
 int dy[4] = { 0,0,1,-1 };
 int sx, sy;
 int ex, ey;
 int vis[15][15] = { 0 };
 int dist[15][15] = { 0 };
 int cnt[15][15] = { 0 };
 struct info
 {
     int x; int y;
 };

 void bfs(vector<vector<int> >& CityMap, int n, int m)
 {
     queue<info> qNodes;
     qNodes.push({ sx,sy });
     cnt[sx][sy] = 1;
     dist[sx][sy] = 0;
     while (!qNodes.empty())
     {
         auto [i, j] = qNodes.front();
         qNodes.pop();

         for (int k = 0; k < 4; k++)
         {
             int x = i + dx[k];
             int y = j + dy[k];
             if (x >= 0 && x < n && y >= 0 && y < m && CityMap[x][y] != -1)
             {
                 if (dist[x][y] != -1 && dist[x][y] == dist[i][j] + 1)      //被访问过，且能有其他最短路到达
                 {
                     cnt[x][y] += cnt[i][j];
                 }
                 else if (dist[x][y] == -1)       //没有被访问过
                 {
                     dist[x][y] = dist[i][j] + 1;
                     cnt[x][y] += cnt[i][j];
                     qNodes.push({ x,y });
                 }
             }
         }
     }
 }

 int countPath(vector<vector<int> >& CityMap, int n, int m)
 {
     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j < m; j++)
         {
             if (CityMap[i][j] == 1)
             {
                 sx = i;
                 sy = j;
             }
             else if (CityMap[i][j] == 2)
             {
                 ex = i;
                 ey = j;
             }
         }
     }

     memset(dist, -1, sizeof(dist));

     bfs(CityMap, n, m);
     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j < m; j++)
         {
             cout << dist[i][j] << " ";
         }
         cout << endl;
     }
     cout << endl;
     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j < m; j++)
         {
             cout << cnt[i][j] << " ";
         }
         cout << endl;

     }
     return cnt[ex][ey];
 }

 //买卖股票的最好时机(四)
#include <iostream>
#include <vector>
 using namespace std;

 int main()
 {
     int n, k;
     cin >> n >> k;
     vector<int> prices(n);
     for (int i = 0; i < n; i++)
     {
         cin >> prices[i];
     }

     k = min(k, n / 2);
     //第i天结束后，手中有股票
     vector<vector<int>> f(n + 1, vector<int>(k + 1));

     //第i天结束后，手中无股票
     vector<vector<int>> g(n + 1, vector<int>(k + 1));

     for (int i = 0; i <= k; i++)
     {
         f[0][i] = g[0][i] = -0x3f3f3f3f;
     }

     f[0][0] = -prices[0];
     g[0][0] = 0;
     for (int i = 1; i <= n; i++)
     {
         //j要从0开始：因为只有当卖出时，j才会+1，所以j=0可以等于前一天买入股票时的收益，即f[i-1][j]
         for (int j = 0; j <= k; j++)
         {
             f[i][j] = max(g[i - 1][j] - prices[i - 1], f[i - 1][j]);
             g[i][j] = g[i - 1][j];
             if (j >= 1)
             {
                 g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i - 1]);
             }
         }
     }

     //结果应为最后一天（一行）中的最大值，因为不一定就要进行k笔交易，题目只是说最多只能进行k笔
     int res = 0;
     for (int i = 0; i <= k; i++)
     {
         res = max(res, g[n][i]);
     }

     cout << (res < 0 ? 0 : res) << endl;
     return 0;
 }

 //day 46
//AOE还是单体？
#include <iostream>
#include <vector>
#include <algorithm>
 using namespace std;
 int main()
 {
     long long n, x;
     cin >> n >> x;

     vector<long long> nums(n);
     long long sum = 0;
     for (int i = 0; i < n; i++)
     {
         cin >> nums[i];
         sum += nums[i];
     }

     sort(nums.begin(), nums.end());
     long long tmp = 0;
     long long res = 0;
     if (n - x >= 0)
     {
         tmp = nums[n - x - 1];
         res += tmp * x;        //AOE
         for (int i = n - x; i < n; i++)    //单体攻击
         {
             res += nums[i] - tmp;
         }
     }
     else    //全用单体
     {
         res = sum;
     }

     cout << res << endl;
     return 0;
 }

//kotori和n皇后
#include <iostream>
#include <unordered_set>
 using namespace std;

 unordered_set<long long> row;
 unordered_set<long long> col;
 unordered_set<long long> offset1;
 unordered_set<long long> offset2;
 long long error = 0;

 //注意问的是当前整个棋盘上，是否有有两个皇后会互相攻击，故只要有一个Yes，后面的就都是Yes
 void check()
 {
     long long k;
     cin >> k;
     for (int i = 0; i < k; i++)
     {
         long long x, y;
         cin >> x >> y;

         if (row.count(x) == 1 || col.count(y) == 1
             || offset1.count(y - x) == 1 || offset2.count(x + y) == 1)
         {
             if (error == 0)
             {
                 error = i + 1;
             }
         }

         row.insert(x);
         col.insert(y);
         offset1.insert(y - x);
         offset2.insert(x + y);
     }

 }

 int main()
 {
     check();
     long long t;
     cin >> t;
     while (t--)
     {
         long long q;
         cin >> q;
         if (q >= error && error != 0)
         {
             cout << "Yes" << endl;
         }
         else
         {
             cout << "No" << endl;
         }
     }
     return 0;
 }

 //取金币
 //注意填表顺序，所谓从下往上、从左往右指的是从最后一行开始，从左往右填完一行后往上再填下一行
//所以应该是i=n; i >= 0; i-- 而不是将对i和j的循环互换
 int getCoins(vector<int>& coins)
 {
     int n = coins.size();
     vector<int> cost(n + 2);
     for (int i = 1; i <= n; i++)
     {
         cost[i] = coins[i - 1];
     }
     cost[0] = cost[n + 1] = 1;

     //以下使用cost
     vector<vector<int>> dp(n + 2, vector<int>(n + 2));
     for (int i = n; i >= 1; i--)
     {
         for (int j = i; j <= n; j++)
         {
             for (int k = i; k <= j; k++)
             {
                 dp[i][j] = max(dp[i][j], dp[i][k - 1] + dp[k + 1][j]
                     + cost[k] * cost[i - 1] * cost[j + 1]);
             }
         }
     }

     return dp[1][n];
 }



 //day 47
 //矩阵转置
#include <iostream>
#include <vector>
#include <algorithm>
 using namespace std;
 int main()
 {
     int n, m;
     cin >> n >> m;
     vector<vector<int>> src(n, vector<int>(m));
     vector<vector<int>> dest(m, vector<int>(n));
     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j < m; j++)
         {
             cin >> src[i][j];
         }
     }

     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j < m; j++)
         {
             dest[j][i] = src[i][j];
         }
     }

     for (int i = 0; i < m; i++)
     {
         for (int j = 0; j < n; j++)
         {
             cout << dest[i][j] << " ";
         }
         cout << endl;
     }

     return 0;
 }

 //四个选项
#include <functional>
#include <iostream>
#include <unordered_map>
#include <vector>
 using namespace std;
 int equalOption[15][15] = { 0 };
 int m;
 long long cnt = 0;
 vector<int> ans;

 //遍历之前所有填过的位置进行对比,j表示当前cur位置想填的选项
 bool isSame(int cur, int j)
 {
     for (int i = 0; i < cur; i++)
     {
         if (equalOption[i][j] == 1 && ans[i] != j)
         {
             return false;
         }
     }

     return true;
 }

 //题号从0开始，填第cur道题的答案
 void dfs(vector<int>& optionCnt, int cur)
 {
     if (cur >= 12)
     {
         cnt++;
         return;
     }

     for (int i = 0; i < 4; i++)
     {
         if (optionCnt[i] != 0)
         {
             if (!isSame(cur, i))
             {
                 continue;
             }

             ans.push_back(i);
             optionCnt[i]--;
             dfs(optionCnt, cur + 1);
             ans.pop_back();
             optionCnt[i]++;
         }
     }
 }

 int main()
 {
     vector<int> optionCnt(4);
     //0、1、2、3分别代表四个选项
     for (int i = 0; i < 4; i++)
     {
         cin >> optionCnt[i];
     }
     cin >> m;

     while (m--)
     {
         int x, y;
         cin >> x >> y;
         equalOption[x][y] = equalOption[y][x] = 1;      //需要双向
     }

     dfs(optionCnt, 0);

     cout << cnt << endl;
     return 0;
 }

 //接雨水
 long long maxWater(vector<int>& arr)
 {
     int n = arr.size();
     vector<int> leftMax(n);
     vector<int> rightMax(n);

     leftMax[0] = arr[0];
     for (int i = 1; i < n; i++)
     {
         leftMax[i] = max(leftMax[i - 1], arr[i]);
     }

     rightMax[n - 1] = arr[n - 1];
     for (int i = n - 2; i >= 0; i--)
     {
         rightMax[i] = max(rightMax[i + 1], arr[i]);
     }

     for (int i = 0; i < n; i++)
     {
         cout << leftMax[i] << " " << rightMax[i] << endl;
     }

     long long res = 0;
     for (int i = 1; i < n - 1; i++)
     {
         int tmp = min(leftMax[i], rightMax[i]) - arr[i];
         res += tmp > 0 ? tmp : 0;
     }

     return res;
 }


 //day 48
 //疯狂的自我检索者
#include <iostream>
 using namespace std;

 int main()
 {
     int n, m;
     cin >> n >> m;

     int sum = 0;
     for (int i = 0; i < n - m; i++)
     {
         int a;
         cin >> a;
         sum += a;
     }

     double minScore = (double)(sum + m) / n;
     double maxScore = (double)(sum + 5 * m) / n;

     printf("%.5lf %.5lf", minScore, maxScore);
     return 0;
 }

 //栈和排序
     //1、不断入栈，直到找到最大的，加入结果集后
    //2、找第二大的，若在栈中，则一直出栈；若在栈外，则如步骤1
 vector<int> solve(vector<int>& a)
 {
     int n = a.size();
     int cur = n;
     vector<int> res;
     vector<int> stack;
     vector<int> hash(n + 1);      //标记已入栈的元素
     int pos = 0;

     //先更新目标值后再出栈，若先出栈后续的更新会很复杂
     while (pos < n)
     {
         stack.push_back(a[pos]);
         hash[a[pos]] = 1;

         while (hash[cur] == 1)     //检查已入栈的元素要出到“几”(不包括“几”)
         {
             cur--;
         }

         //此时如果下一个元素已在栈中，那么stack.back() >= cur一定成立
         while (!stack.empty() && stack.back() >= cur)
         {
             res.push_back(stack.back());
             stack.pop_back();
         }
         pos++;
     }

     return res;
 }

 //加减
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
 using namespace std;

 //1、贪心：两个元素的差值尽可能的小 --> 排序
 //2、枚举：每一个区间
 //3、数学：一段有序的区间中，变成哪个元素所需的变化次数最小 --> 中间的那个（数轴上可证明，因为两数差值 <=> 两点间距离）
 //4、优化计算花费：列出公式后，发现可以用前缀和
 //5、优化区间枚举：滑动窗口

 int main()
 {
     long long n, k;
     cin >> n >> k;

     vector<long long> nums(n + 1);
     for (int i = 1; i <= n; i++)
     {
         cin >> nums[i];
     }

     //1、排序
     sort(nums.begin(), nums.end());

     //2、前缀和
     vector<long long> prefix(n + 1);
     for (int i = 1; i <= n; i++)
     {
         prefix[i] = prefix[i - 1] + nums[i];
     }

     //3、滑动窗口枚举
     long long left = 1;
     long long right = 1;
     long long res = 1;
     while (right <= n)
     {
         long long mid = (right - left) / 2 + left;

         long long cost = (mid - left) * nums[mid] - (prefix[mid - 1] - prefix[left - 1])
             + (prefix[right] - prefix[mid]) - (right - mid) * nums[mid];


         if (cost <= k)
         {
             right++;
         }
         else
         {
             res = max(res, right - left);
             left++;
         }
     }
     res = max(res, right - left);

     cout << res << endl;
     return 0;
 }
